#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

#define flr(x,l,r) for (int x = l; x <= r; ++ x)
#define frl(x,r,l) for (int x = r; x >= l; -- x)
#define fmp(x,t) for (int x = h[t]; ~x; x = ne[x])
#define LL long long 
#define mt memset 
#define szf sizeof
#define INF 0x3f3f3f3f
#define in(x) scanf("%d", &x)
#define out(x) printf("%d", x)
#define inll(x) scanf("%lld", &x)
#define outll(x) printf("%lld", x)
#define pn printf("\n")
#define con continue
#define bk break
#define vc vector 
#define pb push_back
#define sz size
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 100010, M = 2000010;

int n, m;
int h[N], rh[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
int w[N];
int q[N];
bool st[N];

void add(int h[], int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa(int h[], int dist[], int type) {
    int hh = 0, tt = 1;
    if (type) {
        mt(dist, -0x3f, szf dmax);
        dist[n] = w[n];
        q[0] = n;
    }
    else {
        mt(dist, 0x3f, szf dmin);
        dist[1] = w[1];
        q[0] = 1;
    }
    
    while (hh != tt) {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        
        fmp (i, t) {
            int j = e[i];
            if ((!type && dist[j] > min(dist[t], w[j])) || (type && dist[j] < max(dist[t], w[j]))) {
                if (type) dist[j] = max(dist[t], w[j]);
                else dist[j] = min(dist[t], w[j]);
                
                if (!st[j]) {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

int main() {
	in(n), in(m);
	
	flr (i, 1, n) in(w[i]);
	
	mt(h, -1, szf h), mt(rh, -1, szf rh);
	while (m -- ) {
	    int a, b, c;
	    in(a), in(b), in(c);
	    add(h, a, b), add(rh, b, a);
	    if (c == 2) add(h, b, a), add(rh, a, b);
	}
	
	spfa(h, dmin, 0), spfa(rh, dmax, 1);
	
	int res = -INF;
	flr (i, 1, n) res = max(res, dmax[i] - dmin[i]);
	
	out(res), pn;
	
	return 0;
}